import java.util.Scanner;

public class test {
    //递归求和
    //递归求 1 + 2 + 3 + ... + 10
    public static int sum(int n) {
        if(n==1)
        {
            return 1;
        }
        int x=n+sum(n-1);
        return x;
    }

    public static void main0(String[] args) {
        int k=sum(10);
        System.out.println(k);
    }

    //递归打印数字的每一位
    //eg：1234 打印1,2,3,4
    public static void print(int n) {

        int i=n%10;
       if(n/10!=0)
       {
           print(n/10);
       }
        System.out.print(i+" ");
    }

    public static void main1(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        print(n);
    }

    //写一个递归方法，输入一个非负整数，返回组成它的数字之和
    public static int fsum(int n) {
        int i=n%10;//12%10=2,
        if(n/10!=0)
        {
            i+=fsum(n/10);
        }
        return i;
    }

    public static void main2(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int sum=fsum(n);
        System.out.println(sum);
    }


    //递归求n的阶乘
    public static int jc(int n) {
        if(n==1)
        {
            return 1;
        }
        else
        {
            n*=jc(n-1);
            return n;
        }
    }

    public static void main3(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(true)
        {
            int n=scanner.nextInt();
            int x=jc(n);
            System.out.println(n+"的阶乘为："+x);
        }
    }

    public static void move(char pos1 ,char pos2) {
        //模拟实现盘子的移动
        //pos1移动到pos2，这里pos1、pos2只是一个代指
        // 比如你想移动A上方的一个盘子到C,你传参就是pos1=A,pos2=B
        System.out.print(pos1+"->"+pos2+" ");
    }

    public static void hanNuoTa(int n,char pos1 ,char pos2,char pos3) {
        //n表示要移动的盘子个数
        //pos1起始位置、pos2中转位置、pos3目标位置
        //因为移动过程中，目标位置、中转位置是会变的
        if(n==1)
        {
            move(pos1,pos3);
        }
        else
        {
            hanNuoTa(n-1,pos1,pos3,pos2);
            //起始位置移动n-1个到中转位置
            move(pos1,pos3);//n-1个移动完，将起始位置最大的1个移动到目标位置
            //问题转换成：pos2是起始位置，pos3目标位置，pos1中转位置，如何将n-1个盘，从pos2移动到pos3
            hanNuoTa(n-1,pos2,pos1,pos3);
        }
    }

    public static void main4(String[] args) {
        hanNuoTa(1,'A','B','C');
        System.out.println();
        hanNuoTa(2,'A','B','C');
        System.out.println();
        hanNuoTa(3,'A','B','C');
        System.out.println();
        hanNuoTa(4,'A','B','C');
        System.out.println();
    }


    public static int frogJump(int n) {
        if(n==1||n==2)
        {
            return n;
        }
        else{
            return frogJump(n-1)+frogJump(n-2);
        }
    }

    public static void main(String[] args) {
        int x=frogJump(1);
        System.out.println(x);
        int y=frogJump(2);
        System.out.println(y);
        int z=frogJump(3);
        System.out.println(z);
        int m=frogJump(4);
        System.out.println(m);
    }
}
